"""
1233. 删除子文件夹
中等
相关标签
premium lock icon
相关企业
提示
你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。folder[j] 的子文件夹必须以 folder[j] 开头，后跟一个 "/"。例如，"/a/b" 是 "/a" 的一个子文件夹，但 "/b" 不是 "/a/b/c" 的一个子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。


示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。
示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。
示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]


提示：

1 <= folder.length <= 4 * 104
2 <= folder[i].length <= 100
folder[i] 只包含小写字母和 '/'
folder[i] 总是以字符 '/' 起始
folder 每个元素都是 唯一 的
"""
from typing import List

class TrieNode:
    def __init__(self):
        # self.times = 0
        # self.str = None
        self.next = {}  # 在__init__中初始化
        self.is_folder = False  # 标记是否为文件夹路径结尾



class Solution:
    def removeSubfolders_Res1(self, folder: List[str]) -> List[str]:
        # 构建前缀树
        root = TrieNode()

        # 将文件夹路径按长度排序，确保父文件夹先处理
        folder.sort()

        result = []
        for path in folder:
            folders = path.split('/')
            current = root
            is_subfolder = False

            # 遍历路径中的每个部分
            for f in folders:
                if f == '':
                    continue

                # 如果当前节点已经是某个文件夹的结尾，说明当前路径是子文件夹
                if current.is_folder:
                    is_subfolder = True
                    break

                # 如果该部分不存在，创建新节点
                if f not in current.next:
                    current.next[f] = TrieNode()

                # 移动到下一个节点
                current = current.next[f]

            # 如果不是子文件夹，则标记为文件夹结尾并加入结果
            if not is_subfolder:
                current.is_folder = True
                result.append(path)

        return result

    def removeSubfolders(self, folder: List[str]) -> List[str]:
        root = self.timeNode()
        for i in folder:
            f = i.split('/')
            temp = root
            for f0 in f:
                if f0 in temp.next:
                    temp.next[f0].times+=1
                    temp = temp.next[f0].next
                else:
                    node = self.timeNode()
                    node.str = f0
                    node.times = 1
                    temp.next[f0] = node
                temp = temp.next[f0]
        print(root)
    def removeSubfolders_Res2(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for s in folder[1:]:  # 切片可以用 for i in range(1, n) 代替，做到 O(1) 空间
            last = ans[-1]
            #不是以他开头，或者以他开头但是没有用/结尾都认为是新的， s[len(last)] != '/'作用是区分/a和/ab,/a是/ab开头但是他不是/ab的上级文件夹
            if not s.startswith(last) or s[len(last)] != '/':
            # if not s.startswith(last):
                ans.append(s)
        return ans
    class timeNode:
        times = 0
        str = None
        next = {}
if __name__ == '__main__':
    print(Solution().removeSubfolders(["/a","/a/b","/c/d","/c/d/e","/c/f"]))
    # print(Solution().removeSubfolders_Res2(["/a/b/c","/a/b/ca","/a/b/d"]))
